Genetic variants underlying reduced male reproductive performance have been identified in humans and model organisms, most of them compromising semen quality. Occasionally, male fertility is severely compromised although semen analysis remains without any apparent pathological findings (i.e., idiopathic subfertility). Artificial insemination (AI) in most cattle populations requires close examination of all ejaculates before insemination. Although anomalous ejaculates are rejected, insemination success varies considerably among AI bulls. In an attempt to identify genetic causes of such variation, we undertook a genome-wide association study (GWAS). Imputed genotypes of 652,856 SNPs were available for 7962 AI bulls of the Fleckvieh (FV) population. Male reproductive ability (MRA) was assessed based on 15.3 million artificial inseminations. The GWAS uncovered a strong association signal on bovine chromosome 19 (P = 4.08×10−59). Subsequent autozygosity mapping revealed a common 1386 kb segment of extended homozygosity in 40 bulls with exceptionally poor reproductive performance. Only 1.7% of 35,671 inseminations with semen samples of those bulls were successful. None of the bulls with normal reproductive performance was homozygous, indicating recessive inheritance. Exploiting whole-genome re-sequencing data of 43 animals revealed a candidate causal nonsense mutation (rs378652941, c.483C>A, p.Cys161X) in the transmembrane protein 95 encoding gene TMEM95 which was subsequently validated in 1990 AI bulls. Immunohistochemical investigations evidenced that TMEM95 is located at the surface of spermatozoa of fertile animals whereas it is absent in spermatozoa of subfertile animals. These findings imply that integrity of TMEM95 is required for an undisturbed fertilisation. Our results demonstrate that deficiency of TMEM95 severely compromises male reproductive performance in cattle and reveal for the first time a phenotypic effect associated with genomic variation in TMEM95.